#include<iostream>
#include<vector>

using namespace std;

bool canPartition(vector<int>& nums) {
    int n = nums.size();
    int sum = 0;
    for (auto it : nums)
        sum += it;
    if (sum % 2) return false;
    sum /= 2;

    vector<int> f(sum + 1);
    f[0] = true;
    for (int i = 0; i < n; i++)
        for (int j = sum; j >= nums[i]; j--)
            f[j] = f[j] || f[j - nums[i]];
    return f[sum];
}